package com.sicheng.lc.lc笔试.美团篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/19 21:32
 */
public class 蛇形填数 {
    /**
     * 输入两个整数 n 和 m，输出一个 n 行 m 列的矩阵，将数字 1 到 n×m 按照回字蛇形填充至矩阵中。
     * <p>
     * 具体矩阵形式可参考样例。
     * <p>
     * 输入格式
     * 输入共一行，包含两个整数 n 和 m。
     * <p>
     * 输出格式
     * 输出满足要求的矩阵。
     * <p>
     * 矩阵占 n 行，每行包含 m 个空格隔开的整数。
     * <p>
     * 数据范围
     * 1≤n,m≤100
     * 输入样例：
     * 3 3
     * 输出样例：
     * 1 2 3
     * 8 9 4
     * 7 6 5
     */

    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int[][] nums = new int[n][m];

        s2(nums);

        for (int[] num : nums) {
            for (int i : num) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    static void s2(int[][] nums) {
        int i = 0, j = 0;
        nums[i][j] = 1;
        int k = 0;
        while (k <= 4) {
            int x = d[k][0] + i;
            int y = d[k][1] + j;
            while (x >= 0 && x < n && y >= 0 && y < m && nums[x][y] == 0) {
                nums[x][y] = nums[i][j] + 1;
                if (nums[x][y] == n * m)
                    return;
                i = x;
                j = y;
                x = d[k][0] + x;
                y = d[k][1] + y;
            }
            k++;
            k %= 4;
        }
    }

    private static void s1(int[][] nums) {
        nums[0][0] = 1;
        dfs(nums, 0, 0);
    }


    //
    static int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static void dfs(int[][] nums, int i, int j) {

        if (nums[i][j] == n * m) {
            return;
        }

        for (int[] ints : d) {
            int x;
            int y;
            if (j + 1 < m && ints[1] == 1 && nums[i][j + 1] == 0 && i - 1 >= 0 && nums[i - 1][j] == 0) {
                x = i - 1;
                y = j;
            } else {
                x = i + ints[0];
                y = j + ints[1];
            }

            if (x >= 0 && x < n && y >= 0 && y < m && nums[x][y] == 0) {
                nums[x][y] = nums[i][j] + 1;
                dfs(nums, x, y);
                break;
            }
        }

    }
}
